package com.springboot.java.design.search;

import java.util.HashMap;

/**
 * @Author: TongRui乀
 * @Date: 2020-09-02 10:00
 * @description：
 *  找出数组中出现次数超过一半的数，现在有一个数组，
 *  已知一个数出现的次数超过了一半，
 *  请用O(n)的复杂度的算法找出这个数。
 *
 */
public class MaxCount {

    public static void main(String[] args) {

        int[] arr = {1,2,3,4,5,5,5,5,7,8,9,0,5};

        HashMap<Integer, Integer> map = new HashMap<>();

        int max = 0;
        int maxCount = 0;

        for (int i = 0; i < arr.length; i++) {

            if(map.containsKey(arr[i])){
                Integer count = map.get(arr[i]);
                map.put(arr[i], ++count);
                if(count > maxCount){
                    maxCount = count;
                    max = arr[i];
                }
            }else {
                map.put(arr[i], 1);
            }
        }

        System.out.println(max);

    }

}
